package com.lims.algorithm.algset.graph;

import org.apache.commons.lang3.StringUtils;
import org.springframework.util.CollectionUtils;

import java.lang.reflect.Array;
import java.time.temporal.IsoFields;
import java.util.*;
import java.util.List;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * <功能简述> 有向图 —— 邻接表 十字链表实现
 *
 * @author lims
 * @date 2020-08-27 19:34
 */
public class DGraphCrossList<T> {
    /**
     * 顶点类
     */
    class Vertex {
        // 数据
        T data;
        // 第一条边
        Edge firstEdge;
        // 第一条逆向边
        ReverseEdge firstRvsEdge;
        // 入度
        int inDegree;
        // 出度
        int outDegree;

        public Vertex(T data, Edge firstEdge, ReverseEdge firstRvsEdge) {
            this.data = data;
            this.firstEdge = firstEdge;
            this.firstRvsEdge = firstRvsEdge;
        }

        // 入度加1
        public void incrInDegree() {
            inDegree++;
        }

        // 出度加1
        public void incrOutDegree() {
            outDegree++;
        }

        // 入度减1
        public void decrInDegree() {
            inDegree--;
        }

        // 出度减1
        public void decrOutDegree() {
            outDegree--;
        }
    }

    /**
     * 边 类
     */
    class Edge {
        // 指向的结点
        int pVex;
        // 下一条边
        Edge nextEdge;
        // 边权重
        int weight;

        public Edge(int pVex, Edge nextEdge, int weight) {
            this.pVex = pVex;
            this.nextEdge = nextEdge;
            this.weight = weight;
        }
    }

    /**
     * 逆向边 类（用于构造逆邻接表，十字链表）
     */
    class ReverseEdge {
        // 边来源结点
        int rVes;
        // 下一条边
        ReverseEdge nextRvsEdge;
        // 边权重
        int weight;

        public ReverseEdge(int rVes, ReverseEdge nextRvsEdge, int weight) {
            this.rVes = rVes;
            this.nextRvsEdge = nextRvsEdge;
            this.weight = weight;
        }
    }

    /**
     * 最大值
     */
    private static final int INF = Integer.MAX_VALUE;

    /**
     * 顶点集合
     */
    List<Vertex> vertexs;
    /**
     * 边数
     */
    int eNum;
    /**
     * 是否访问
     */
    boolean[] isVisited;

    /**
     * 构造函数
     *
     * @param n 顶点数
     */
    public DGraphCrossList(int n) {
        vertexs = new ArrayList<>(n);
        eNum = 0;
        isVisited = new boolean[n];
    }

    /**
     * 添加顶点
     *
     * @param ver 顶点的数据
     */
    public void addVer(T ver) {
        Vertex vertex = new Vertex(ver, null, null);
        vertexs.add(vertex);
    }

    /**
     * 添加边 v1 —— v2 （有向图）
     *
     * @param v1     边出来的结点
     * @param v2     边指向的结点
     * @param weight 边权重
     */
    public void addEdge(int v1, int v2, int weight) {
        // v1指向v2的边
        Edge e2 = new Edge(v2, null, weight);
        // v1指向v2的逆向边
        ReverseEdge re2 = new ReverseEdge(v1, null, weight);

        //顶点v1
        Vertex vertex1 = vertexs.get(v1);
        //顶点v2
        Vertex vertex2 = vertexs.get(v2);

        // v1 —— v2边（v1顶点）
        if (vertex1.firstEdge == null) {
            vertex1.firstEdge = e2;
        } else {
            linkEdge(vertex1.firstEdge, e2);
        }
        // v1——v2逆向边（v2顶点）
        if (vertex2.firstRvsEdge == null) {
            vertex2.firstRvsEdge = re2;
        } else {
            linkRvsEdge(vertex2.firstRvsEdge, re2);
        }

        // v1 出度 +1
        vertex1.incrOutDegree();
        // v2 入度 +1
        vertex2.incrInDegree();
        // 边数 +1
        eNum++;
    }

    /**
     * 将边“tailEdge”链接到头为“firstEdge”的链表尾部
     *
     * @param firstEdge 链表头结点
     * @param tailEdge  需要链接的结点
     */
    private void linkEdge(Edge firstEdge, Edge tailEdge) {
        if (firstEdge.nextEdge == null) {
            firstEdge.nextEdge = tailEdge;
            return;
        }
        linkEdge(firstEdge.nextEdge, tailEdge);
    }

    /**
     * 将边“tailRvsEdge”链接到头为“firstRvsEdge”的链表尾部（逆向边）
     *
     * @param firstRvsEdge
     * @param tailRvsEdge
     */
    private void linkRvsEdge(ReverseEdge firstRvsEdge, ReverseEdge tailRvsEdge) {
        ReverseEdge rvsEdge = firstRvsEdge;
        while (rvsEdge.nextRvsEdge != null) {
            rvsEdge = rvsEdge.nextRvsEdge;
        }
        rvsEdge.nextRvsEdge = tailRvsEdge;
    }

    /**
     * 返回值
     *
     * @param index
     * @return
     */
    public T getValue(int index) {
        return vertexs.get(index).data;
    }

    /**
     * 返回<v1,v2>边的权重</>
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1, int v2) {
        Edge edge = vertexs.get(v1).firstEdge;
        while (edge != null) {
            if (edge.pVex == v2) {
                return edge.weight;
            }
            edge = edge.nextEdge;
        }
        return -1;
    }

    /**
     * 显示十字链表
     */
    public void show() {
        System.out.println("十字链表显示：");
        // 逆邻接表最大链表数（整齐打印）
        int rvsEdgeLinkMaxNum = getRvsEdgeLinkMaxNum();
        for (int i = 0; i < vertexs.size(); i++) {
            ReverseEdge firstRvsEdge = vertexs.get(i).firstRvsEdge;
            Edge firstEdge = vertexs.get(i).firstEdge;

            // 打印逆邻接表边链表
            reversePrintRvsEdgeLink(firstRvsEdge, rvsEdgeLinkMaxNum);
            // 打印顶点
            System.out.print("<--:" + i + "(" + vertexs.get(i).data + "):-->");
            // 打印邻接表
            orderPrintEdgeLink(firstEdge);
            System.out.printf("\n");
        }
    }

    /**
     * 倒序打印逆邻接表
     *
     * @param head 头结点
     */
    private void reversePrintRvsEdgeLink(ReverseEdge head, int maxRvsEdgeNum) {
        List<String> list = new ArrayList<>();
        Stack<String> stack = new Stack<>();
        while (head != null) {
            stack.push(head.rVes + "(" + vertexs.get(head.rVes).data + ")");
            head = head.nextRvsEdge;
        }
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        // 右对齐打印
        System.out.printf("%" + (maxRvsEdgeNum * 6 - 2) + "s", String.join("<-", list));
    }

    /**
     * 顺序打印邻接表
     */
    private void orderPrintEdgeLink(Edge head) {
        if (head == null) {
            return;
        }
        System.out.print(head.pVex + "(" + vertexs.get(head.pVex).data + ")");
        orderPrintEdgeLink(head.nextEdge);
    }

    /**
     * 返回链表结点数
     */
    private int getRvsLinkNum(ReverseEdge head) {
        if (head == null) {
            return 0;
        }
        return 1 + getRvsLinkNum(head.nextRvsEdge);
    }

    /**
     * 找到链表最大个数
     */
    private int getRvsEdgeLinkMaxNum() {
        int maxNum = 0;
        for (int i = 0; i < vertexs.size(); i++) {
            int rvsLinkNum = getRvsLinkNum(vertexs.get(i).firstRvsEdge);
            if (maxNum < rvsLinkNum) {
                maxNum = rvsLinkNum;
            }
        }
        return maxNum;
    }

    /**
     * 第一个邻接点
     */
    public int getFirstAjcVer(int index) {
        Vertex vertex = vertexs.get(index);
        return vertex.firstEdge == null ? -1 : vertex.firstEdge.pVex;
    }

    /**
     * 下一个邻接点
     */
    public int getNextAjcVer(int v1, int v2) {
        if (v1 == v2) {
            return v1;
        }
        Vertex vertex = vertexs.get(v1);
        Edge firstEdge = vertex.firstEdge;
        while (firstEdge != null) {
            if (firstEdge.pVex == v2) {
                return firstEdge.nextEdge == null ? -1 : firstEdge.nextEdge.pVex;
            }
            firstEdge = firstEdge.nextEdge;
        }
        return -1;
    }

    /**
     * 下一个未访问过的邻接顶点
     */
    public int getNextAjcNoAccessVer(int index) {
        Vertex vertex = vertexs.get(index);
        Edge firstEdge = vertex.firstEdge;
        while (firstEdge != null) {
            if (!isVisited[firstEdge.pVex]) {
                return firstEdge.pVex;
            }
            firstEdge = firstEdge.nextEdge;
        }
        return -1;
    }

    public void clearIsVisited() {
        isVisited = new boolean[vertexs.size()];
    }

    /**
     * 未访问的邻接点集合
     *
     * @param v
     * @return
     */
    public List<Integer> getUnVisiteds(int v) {
        ArrayList<Integer> unVisiteds = new ArrayList<>();
        Edge firstEdge = vertexs.get(v).firstEdge;
        while (firstEdge != null) {
            if (!isVisited[firstEdge.pVex]) {
                unVisiteds.add(firstEdge.pVex);
            }
            firstEdge = firstEdge.nextEdge;
        }
        return unVisiteds;
    }

    /**
     * 深度优先遍历
     */
    public void DFS() {
        System.out.println("深度优先遍历：");
        List<T> dfsResults = new ArrayList<>();
        for (int i = 0; i < vertexs.size(); i++) {
            if (!isVisited[i]) {
                DFS(isVisited, i, dfsResults);
            }
        }
        System.out.print(StringUtils.join(dfsResults, "->"));
        System.out.printf("\n");
    }

    private void DFS(boolean[] isVisited, int i, List<T> dfsResults) {
        dfsResults.add(getValue(i));
        isVisited[i] = true;
        int ajcVer = getFirstAjcVer(i);
        while (ajcVer != -1) {
            if (!isVisited[ajcVer]) {
                DFS(isVisited, ajcVer, dfsResults);
            }
            ajcVer = getNextAjcVer(i, ajcVer);
        }
    }

    /**
     * 广度优先遍历
     */
    public void BFS() {
        System.out.println("广度优先遍历：");
        for (int i = 0; i < vertexs.size(); i++) {
            if (!isVisited[i]) {
                BFS(isVisited, i);
            }
        }
        System.out.printf("\n");
    }

    private void BFS(boolean[] isVisited, int i) {
        // 队列头
        int h;
        // 邻接点
        int ajcVer;
        Queue<Integer> queue = new LinkedBlockingQueue<>();
        System.out.print(getValue(i));
        isVisited[i] = true;
        queue.offer(i);
        while (!queue.isEmpty()) {
            h = queue.poll();
            ajcVer = getNextAjcNoAccessVer(h);
            while (ajcVer != -1) {
                if (!isVisited[ajcVer]) {
                    System.out.print("->");
                    System.out.print(getValue(ajcVer));
                    isVisited[ajcVer] = true;
                    queue.offer(ajcVer);
                }
                ajcVer = getNextAjcNoAccessVer(h);
            }
        }
    }

    /**
     * 深度优先遍历 非递归
     */
    public void DFSNoRecur() {
        List<T> dfsResults = new ArrayList<>();
        for (int i = 0; i < vertexs.size(); ++i) {
            if (!isVisited[i]) {
                DFSNoRecur(isVisited, i, dfsResults);
            }
        }
        System.out.printf("深度优先遍历（非递归）:%s\n", StringUtils.join(dfsResults, "->"));
    }

    private void DFSNoRecur(boolean[] isVisited, int v, List<T> dfsResults) {
        Stack<Integer> stack = new Stack<>();
        stack.push(v);
        isVisited[v] = true;
        while (!stack.isEmpty()) {
            int index = stack.peek().intValue();
            int ajc = getNextAjcNoAccessVer(index);
            if (ajc == -1) {
                // 到底了
                stack.pop();
            } else {
                dfsResults.add(getValue(ajc));
                isVisited[ajc] = true;
                // 类似递归到底
                stack.push(ajc);
            }
        }
    }


    /**
     * DFS2方法
     *
     * @param v 起点
     */
    public void DFS2(int v) {
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> dependencyMap = new HashMap<>();
        List<T> dfsR = new ArrayList<>();
        DFS2(v, stack, dependencyMap, dfsR);
        System.out.printf("深度优先遍历2（%d）：%s\n", v, StringUtils.join(dfsR, "->"));
    }

    private void DFS2(int v, Stack<Integer> stack, Map<Integer, Integer> dependencyMap, List<T> dfsR) {
        stack.push(v);
        while (!stack.isEmpty()) {
            int pop = stack.pop().intValue();
            dfsR.add(getValue(pop));
            isVisited[pop] = true;
            List<Integer> unVisiteds = getUnVisiteds(pop);
            unVisiteds.forEach(uv -> stack.push(uv));
        }
    }


    /**
     * 拓扑排序：
     * （将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。）
     * <p>
     * 步骤：
     * 1. 构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological)；
     * 2. 把所有没有依赖顶点的节点放入Q；
     * 3. 当Q还有顶点的时候，执行下面步骤：
     * 3.1 从Q中取出一个顶点n(将n从Q中删掉)，并放入T(将n加入到结果集中)；
     * 3.2 对n每一个邻接点m(n是起点，m是终点)；
     * 3.2.1 去掉边<n,m>;
     * 3.2.2 如果m没有依赖顶点，则把m放入Q;
     * 注：顶点A没有依赖顶点，是指不存在以A为终点的边。
     *
     * @return 返回值
     * *    -1 -- 失败(由于内存不足等原因导致)
     * *     0 -- 成功排序，并输入结果
     * *     1 -- 失败(该有向图是有环的)
     */
    public int topologicalSort() {
        if (!graphIsDAG()) {
            return 1;
        }
        // 拓扑排序结果
        List<T> tops = new ArrayList<>();
        // 顶点入度数组
        List<Integer> inDegrees = new ArrayList<>();
        vertexs.stream().forEach(vertex -> inDegrees.add(vertex.inDegree));
        // 辅助队列
        Queue<Integer> queue = new LinkedBlockingQueue<>();

        // 入度为0的顶点入队列
        Stream.iterate(0, t -> t + 1).limit(inDegrees.size())
                .forEach(i -> {
                    if (0 == inDegrees.get(i)) {
                        queue.offer(i);
                    }
                });

        while (!queue.isEmpty()) {
            int j = queue.poll().intValue();
            tops.add(vertexs.get(j).data);
            Edge firstEdge = vertexs.get(j).firstEdge;
            while (firstEdge != null) {
                inDegrees.set(firstEdge.pVex, inDegrees.get(firstEdge.pVex) - 1);
                if (0 == inDegrees.get(firstEdge.pVex)) {
                    queue.offer(firstEdge.pVex);
                }
                firstEdge = firstEdge.nextEdge;
            }
        }

        // 打印拓扑排序结果
        System.out.println(StringUtils.join(tops, "--"));
        return 0;
    }

    /**
     * 判断图是否是DAG
     */
    public boolean graphIsDAG() {
        // 顶点入度数组
        List<Integer> inDegrees = new ArrayList<>();
        vertexs.stream().forEach(vertex -> inDegrees.add(vertex.inDegree));

        // 辅助队列
        Queue<Integer> queue = new LinkedBlockingQueue<>();
        // 入度为0的顶点入队列
        inDegrees.stream().filter(inDegree -> inDegree == 0).forEach(inDegree -> queue.offer(inDegree));

        while (!queue.isEmpty()) {
            // 出队列
            int j = queue.poll().intValue();
            Edge firstEdge = vertexs.get(j).firstEdge;
            // 对邻接点入度 -1
            while (firstEdge != null) {
                inDegrees.set(firstEdge.pVex, inDegrees.get(firstEdge.pVex) - 1);
                if (0 == inDegrees.get(firstEdge.pVex)) {
                    queue.offer(firstEdge.pVex);
                }
                firstEdge = firstEdge.nextEdge;
            }
        }

        // 入度为0的顶点数
        int zeroDegreeNum = inDegrees.stream().filter(i -> 0 == i).collect(Collectors.toList()).size();
        if (vertexs.size() > zeroDegreeNum) {
            return false;
        }
        return true;
    }

    /**
     * 拓扑排序2
     * 拓扑结果tops 入度数组inDgrees
     * 1. 入度为0的点入队列
     * 2.队列投h出队列，并给h出度的邻接点的入度 -1，如果-1后入度为0，则入队列
     *
     * @return
     */
    public int topologicalSort2() {
        List<T> tops = new ArrayList<>(vertexs.size());
        int[] inDegrees = (int[]) Array.newInstance(int.class, vertexs.size());
        Queue<Integer> queue = new LinkedBlockingQueue<>();

        // 初始化
        Stream.iterate(0, t -> t + 1).limit(inDegrees.length)
                .forEach(i -> inDegrees[i] = vertexs.get(i).inDegree);

        //1.入度为0点入队
        Stream.iterate(0, t -> t + 1).limit(inDegrees.length)
                .forEach(i -> {
                    if (0 == inDegrees[i]) {
                        queue.offer(i);
                    }
                });

        while (!queue.isEmpty()) {
            int h = queue.poll().intValue();
            tops.add(getValue(h));
            Edge firstEdge = vertexs.get(h).firstEdge;
            // 2. 出队列并给出度结点的入度 -1
            while (firstEdge != null) {
                inDegrees[firstEdge.pVex]--;
                if (inDegrees[firstEdge.pVex] == 0) {
                    queue.offer(firstEdge.pVex);
                }
                firstEdge = firstEdge.nextEdge;
            }
        }

        if (tops.size() != vertexs.size()) {
            System.out.println("图中有环，不是DAG");
            return 1;
        }

        System.out.printf("拓扑排序结果：%s", tops);

        return 0;
    }

    /**
     * Dijkstra最短路径。(每次确定一个点最短路径后，比较经过此条最短路径到这个点邻接点的路径和原来到邻接点的路径，取最小值)
     * 源点v、确定距离标记数组st[]、距离数组distance[]
     * <p>
     * 1.初始化数组
     * 2.遍历找i -> j的距离
     * 2.1 每次找到未确定点的最短距离，确定一个顶点 w
     * 2.2 更新 w 有出度影响到的顶点的距离
     *
     * @param v 源点
     * @return 最小路径到达下标结点时的前一个结点下标（记录最短路径中的详细结点）（每次确定距离的点i，i下游受影响，下游前结点为i）
     */
    public int[] dijkstra(int v) {
        if (v < 0 || v > vertexs.size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        // 确定距离标记数组
        boolean[] st = (boolean[]) Array.newInstance(boolean.class, vertexs.size());
        // 距离数组
        int[] distance = (int[]) Array.newInstance(int.class, vertexs.size());
        // 最短路径中的点的前一个点下标
        int[] minPointPre = (int[]) Array.newInstance(int.class, vertexs.size());

        distance = Arrays.stream(distance).map(d -> d = INF).toArray();
        Stream.iterate(0, t -> t + 1).limit(minPointPre.length)
                .forEach(i -> minPointPre[i] = -1);

        // 1.初始化距离和标记数组
        distance[v] = 0;
        Edge curEdge = vertexs.get(v).firstEdge;
        while (curEdge != null) {
            distance[curEdge.pVex] = curEdge.weight;
            minPointPre[curEdge.pVex] = v;
            curEdge = curEdge.nextEdge;
        }
        st[v] = true;

        // 2.遍历 到j的距离
        for (int i = 0; i < distance.length; ++i) {
            int min = INF;
            int index = -1;

            // 2.1找到未确定的最短距离
            for (int j = 0; j < distance.length; ++j) {
                if (!st[j] && distance[j] < min) {
                    min = distance[j];
                    index = j;
                }
            }

            // 2.2 更新j出度邻接点受影响的距离
            if (index != -1) {
                st[index] = true;
                Edge outgreeEdge = vertexs.get(index).firstEdge;
                while (outgreeEdge != null) {
                    if (!st[outgreeEdge.pVex] &&
                            (min + outgreeEdge.weight) < distance[outgreeEdge.pVex]) {
                        // 新确定点的出度影响了邻接点距离 更新最短距离
                        distance[outgreeEdge.pVex] = min + outgreeEdge.weight;
                        // 记录最短路径中本点的前一个结点，确定点index，本点为index的下一个邻接点
                        minPointPre[outgreeEdge.pVex
                                ] = index;
                    }
                    outgreeEdge = outgreeEdge.nextEdge;
                }
            }
        }

        System.out.printf("最短距离（源点%d）:%s\n", v, Arrays.toString(distance));

        return minPointPre;
    }

    /**
     * 深度优先搜索 —— 最短路径
     *
     * @param v1
     * @param v2
     * @param temp
     * @return
     */
    public int minDistDFS(int v1, int v2, int temp) {
        int min = INF;
        return minDistDFS(v1, v2, temp, min);
    }

    private int minDistDFS(int v1, int v2, int temp, int min) {
        // 到达目标点时返回累计路径
        if (v1 == v2) {
            if (temp < min) {
                min = temp;
            }
            return min;
        }

        // 找邻接点继续向下走
        Edge firstEdge = vertexs.get(v1).firstEdge;
        while (firstEdge != null) {
            // 递归开始深度遍历
            min = minDistDFS(firstEdge.pVex, v2, temp + firstEdge.weight, min);
            firstEdge = firstEdge.nextEdge;
        }
        return min;
    }

    /**
     * 最短路径 —— DFS 打印路径详情
     *
     * @param v1
     * @param v2
     * @return
     */
    public int minDistDFSInfo(int v1, int v2) {
        // 累计起始
        int temp = 0;
        int min = INF;
        // 路径
        int[] path = new int[vertexs.size()];
        // path 索引
        int index = 0;

        Stream.iterate(0, t -> t + 1).limit(path.length)
                .forEach(i -> path[i] = (i == v1) ? -1 : -2);
        return minDistDFSInfo(v1, v2, temp, min, path, index);
    }

    /**
     * @param v1
     * @param v2
     * @param temp
     * @param min
     * @param path
     * @param index
     * @return
     */
    private int minDistDFSInfo(int v1, int v2, int temp, int min, int[] path, int index) {
        if (v1 == v2) {
            if (temp < min) {
                min = temp;
            }
            System.out.printf("路径：%s——路径值：%d\n", Arrays.toString(path), min);
        }
        // 记录路径
        path[index++] = v1;
        Edge firstEdge = vertexs.get(v1).firstEdge;
        while (firstEdge != null) {
            min = minDistDFSInfo(firstEdge.pVex, v2, temp + firstEdge.weight, min, path, index);
            firstEdge = firstEdge.nextEdge;
            // 默认初始值
            path[index--] = -2;
        }
        return min;
    }


    /**
     * 最短路径 —— 深度优先搜索（非递归方式） 有一定问题：间隔才重置路径可能导致漏路径
     * <p>
     * 算法思想：
     * stack:栈，isVisited[]:访问标记，distSum:累计路径
     * 从起点依次入栈，到底；
     * 判断是否到达目标点v2，如到达，记录累计值；
     * 并弹出栈顶（暂时无用），对弹出栈顶的邻接点访问记录重置（以备其他路径使用），取新栈顶的邻接点依次入栈，直到栈空。
     * <p>
     * 步骤：
     * 1.起点入栈
     * 2.判断栈空？ 不为空，第3步，为空，返回min完成。
     * 3.取栈顶peek，peek是否有未访问的邻接点（ajc！=-1?）有，第4步，无，第5步
     * 4.peek邻接点ajc入栈，distSum路径累加<peek,ajc> ，判断到达v2（ajc==v2）？是，distSum替代min
     * 5.判断到达v2（ajc==v2） || 到底了（ajc==-1）？ 是，第6步，否，无操作
     * 6.弹出栈顶pop，distSum 减去 <peek,pop>路径（栈不为空时），对栈顶pop的邻接点访问记录重置（以备其他路径使用），回第2步
     * <p>
     * <p>
     * PS:
     * 栈顶弹出条件：1.到达v2；2.取点到底
     * 栈顶pop弹出后对pop的邻接点访问记录重置（相当于新栈顶peek被pop间隔的点访问记录重置）：让其他路径可访问
     * 暂时不对刚弹出的点重置访问记录（不让重复进入刚刚弹出的路径）
     *
     * @param v1      起点
     * @param v2      终点
     * @param distSum 起始累计路径
     * @return
     */
    public int minDistDFSNoRecur(int v1, int v2, int distSum) {
        int min = INF;
        // 栈顶peek
        int peek;
        // 栈顶pop
        int pop = v1;
        // 邻接点
        int ajc;

        String key = "";
        List<String> list = new ArrayList<>();

        Stack<Integer> stack = new Stack<>();
        // 1.起点入栈
        stack.push(v1);
        isVisited[v1] = true;
        // 2.判断栈为空？
        while (!stack.isEmpty()) {
            // 3.取栈顶邻接点ajc，判断是否有邻接点(有第4步，无第6步)
            peek = stack.peek();
            ajc = getNextAjcNoAccessVer(peek);
            // 4.ajc入栈
            if (ajc != -1) {
                stack.push(ajc);
                isVisited[ajc] = true;
                // distSum路径累加<peek,ajc>
                distSum += getWeight(peek, ajc);
                // 到达v2，替换min路径
                if (ajc == v2) {
                    // 替换最短路径
                    if (distSum < min) {
                        min = distSum;
                    }
                }
            }

            // 5.判断是否到底或者到达v2
            if (ajc == -1 || ajc == v2) {

                // 6.弹出栈顶
                pop = stack.pop();
                isVisited[pop] = false;
                // 减去弹出栈顶点的路径（判空防止弹出栈中最后一个元素）
                if (!stack.isEmpty()) {
                    distSum -= getWeight(stack.peek(), pop);
                }
                // 新栈顶相对旧栈顶的另一个邻接点入栈，如不存在，则循环弹出
                if (!stack.isEmpty()) {
                    peek = stack.peek();
                    ajc = getNextAjcVer(peek, pop);
                    if (ajc != -1) {
                        stack.push(ajc);
                        isVisited[ajc] = true;
                        // distSum路径累加<peek,ajc>
                        distSum += getWeight(peek, ajc);
                    }
                }
            }
        }
        return min;
    }

    /**
     * 最短路径 —— 深度优先搜索 （返回详细路径信息）
     *
     * @param v1
     * @param v2
     * @param distSum
     * @return
     */
    public int[] minDistDFSNoRecurInfo(int v1, int v2, int distSum) {
        int min = INF;
        // 栈顶peek
        int peek;
        // 栈顶pop
        int pop;
        // 邻接点
        int ajc;
        Stack<Integer> stack = new Stack<>();
        // 详细路径集合（每次到达之后存储路径）
        List<String> detailPaths = new ArrayList<>();
        // 具体路径
        int[] minPath = new int[10];
        Object[] minPathTmp;
        stack.push(v1);
        isVisited[v1] = true;
        while (!stack.isEmpty()) {
            peek = stack.peek();
            ajc = getNextAjcNoAccessVer(peek);
            if (ajc != -1) {
                stack.push(ajc);
                isVisited[ajc] = true;
                distSum += getWeight(peek, ajc);
                if (ajc == v2) {
                    if (distSum < min) {
                        min = distSum;
                    }
                    // 到达v2
                    minPathTmp = stack.toArray();
                    minPath = new int[minPathTmp.length];
                    for (int i = 0; i < minPathTmp.length; ++i) {
                        minPath[i] = (int) minPathTmp[i];
                    }
                }
            }

            if (ajc == -1 || ajc == v2) {
                // 6.弹出栈顶
                pop = stack.pop();
                // 减去弹出栈顶点的路径（判空防止弹出栈中最后一个元素）
                if (!stack.isEmpty()) {
                    distSum = distSum - getWeight(stack.peek(), pop);
                }
                // 弹出点的邻接点访问记录重置（以备其他路径使用）
                Edge firstEdge = vertexs.get(pop).firstEdge;
                while (firstEdge != null) {
                    isVisited[firstEdge.pVex] = false;
                    firstEdge = firstEdge.nextEdge;
                }
            }
        }
        printMinDistPath(minPath);
        return minPath;
    }


    /**
     * 根据存储路径前一个结点的数组pre[] 打印最短路径详细信息
     *
     * @param v1
     * @param v2
     * @param pre
     * @return
     */
    public String printMinDistPre(int v1, int v2, int[] pre) {
        Stack<Integer> stack = new Stack<>();
        List<T> list = new ArrayList<>();
        // 最短路径
        int dist = 0;
        stack.push(v2);
        while (v1 != v2) {
            v2 = pre[v2];
            stack.push(v2);
        }
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            if (!stack.isEmpty()) {
                if (getWeight(pop, stack.peek()) != -1) {
                    dist += getWeight(pop, stack.peek());
                }
            }
            list.add(getValue(pop));
        }
        System.out.printf("最短路径结点：%s——最短路径:%d\n", StringUtils.join(list, "->"), dist);
        return StringUtils.join(list, "->");
    }

    /**
     * 正常路径的数组打印路径信息
     *
     * @param path
     */
    public void printMinDistPath(int[] path) {
        List<T> list = new ArrayList<>();
        int distNum = 0;
        for (int i = 0; i < path.length - 1; ++i) {
            distNum += getWeight(path[i], path[i + 1]);
        }
        Stream.iterate(0, t -> t + 1).limit(path.length)
                .forEach(i -> list.add(getValue(path[i])));
        System.out.printf("最短路径结点：%s——最短路径%d\n", StringUtils.join(list, "->"), distNum);
    }

    /****************************************************/
    public static void main(String[] args) {
        // 节点个数
        int n = 7;
        String[] vertexString = {"A", "B", "C", "D", "E", "F", "G"};
        DGraphCrossList<String> dgList = new DGraphCrossList<>(n);
        for (String s : vertexString) {
            dgList.addVer(s);
        }

        /**
         * *
         * *  B -----（20）------> C -（30）-> D
         * *  ^                   ^\
         * *  |                   | \--（4）-> E
         * *（10）               （3）
         * *  |                   |
         * *  A -（1）-> F -（2）-> G
         * *
         */

        // 添加边<A,B> <B,C> <C,D> <C,E> <A,F> <F,G> <G,C>
        dgList.addEdge(0, 1, 10);
        dgList.addEdge(1, 2, 20);
        dgList.addEdge(2, 3, 30);
        dgList.addEdge(2, 4, 4);
        dgList.addEdge(0, 5, 1);
        dgList.addEdge(5, 6, 2);
        dgList.addEdge(6, 2, 3);
        //dgList.addEdge(4, 3, 1);

        dgList.show();
        dgList.DFS();
        dgList.clearIsVisited();
        dgList.BFS();

        // noRecur
        dgList.clearIsVisited();
        dgList.DFSNoRecur();

        // dfs2
        dgList.clearIsVisited();
        dgList.DFS2(0);

        System.out.println(dgList.graphIsDAG());

        dgList.topologicalSort();

        //int[] pre = new int[dgList.vertexs.size()];
        int[] pre = dgList.dijkstra(0);
        dgList.printMinDistPre(0, 3, pre);

        dgList.clearIsVisited();
        System.out.println(dgList.minDistDFS(0, 3, 0));

        System.out.println(dgList.minDistDFSNoRecur(0, 3, 0));
        dgList.minDistDFSNoRecurInfo(0, 3, 0);

        dgList.minDistDFSInfo(0, 3);
    }
}











